1. Field of the Invention
The invention relates to a method and a device for decoding a sequence of physical signals.
2. Description of the Related Art
A method such as this and a device such as this are known from G. D. Forney, The Viterbi-Algorithm, Proceedings of the IEEE, Vol. 61, No. 3, pages 268–278, 1973 (hereinafter referred to as “Forney”).
Forney describes the principles of the so-called Viterbi algorithm.
The Viterbi algorithm, which is frequently used for channel decoding of received physical signals that are subject to disturbances, determines a sequence of signal values along a so-called trellis for the received physical signals. The probability of the determined sequence of signal values corresponding to the sequence of received physical signals is in each case maximized for the sequence of signal values. The procedure which is known from Forney is used to make a decision on a binary basis for each signal value as to whether a signal value has a first binary value or a second binary value.
The procedure which is known from Forney has the particular disadvantage that, during the decoding process, it is not evident how reliable the decision is as to whether the respectively determined signal value actually corresponds to the originally transmitted signal value.
The method from Forney therefore provides no reliability information whatsoever on the quality of the channel decoding process.
In order to improve the method which is known from Forney, it is known from J. Hagenaur, P. Hoeher, A Viterbi Algorithm with Soft-Decision Outputs and its Applications, pages 1680–1686, GLOBECOM, 1989 (hereinafter Hagenaur, et al.) for each determined signal value to be allocated reliability information, which is referred to as a reliability value in the following text, in the course of the channel decoding of the received, noisy (that is to say subject to disturbances) physical signal. The reliability value in each case indicates the reliability of the respective decision which has been made to classify the received signal as the corresponding signal value. This obviously means that the reliability value indicates the extent to which the received signal is similar to the first binary signal value or to the second binary signal value.
The reliability values are formed, for example, as a function of so-called state metrics which are calculated while passing through the trellis in the course of the channel decoding process.
In the method which is known from Hagenauer, et al., the reliability values are determined in the course of a single run through the Viterbi algorithm.
However, it has been found that this procedure is not optimal, especially and in addition with regard to implementation in hardware.
In order to improve the procedure which is known from Hagenauer, et al., the method which is described in J. Hagenauer, Source-Controlled Channel Decoding, IEEE Transaction on Commucications, Vol. 43, No. 9, pages 2449–2457, September 1995 (hereinafter “Hagenauer”) has been developed, in which the Viterbi algorithm is run twice, with only the signal values being determined in the course of the first “run”, and the reliability values being determined in the course of a second run. The result of the first “run” is a “maximum likelihood path” which contains those signal values which have been determined using a path traceback method (backtracing method). The signal values which are located on the maximum likelihood path are used as the decoded physical signals.
In the procedure which is known from Hagenauer, while the second run of the Viterbi algorithm is carried out for a large number of further paths along the entire trellis, with the further paths all having the same length as the maximum likelihood path, namely the length corresponding to the sequence of received physical signals, reliability values are determined and the respective reliability value associated with the signal value is determined as a function of the reliability values of the signal values of the maximum likelihood path and determined reliability values for signal values on the further paths.
This procedure is highly complex and, in practice, cannot be used in real time for the decoding of physical signals, in particular in the field of mobile radio.
It is also known from C. Berrou, et al., A Low complexity Soft-Output Viterbi Decoder Architecture, ICC 93 (hereinafter “Berrou, et al.”), and U.S. Pat. No. 5,406,570 (hereinafter “U.S. Pat. No. '570”) for the Viterbi algorithm not to be carried out for the entire sequence of physical signals but only for a partial sequence and for the signal values to be determined step-by-step along the trellis, with further paths being formed in the course of the Viterbi algorithm and further reliability values being allocated to the determined signal values for these further paths, which further reliability values are compared with the reliability values of the signal values on the maximum likelihood path, which has not yet been completely determined at this time, on the basis of which the final reliability values which are associated with the determined signal values are chosen.
The method which is known from Berrou, et al. and U.S. Pat. No. '570, has the particular disadvantage that convergence of the Viterbi algorithm is not always guaranteed for each of the subregions which are taken into account in order to determine the further paths.
Another method for determining a maximum likelihood path is known from Patent Abstracts of Japan JP 11186914 A (hereinafter “JP11186914 A”). In this method, a first maximum likelihood path is determined, and an additional quasi-maximum likelihood path is then chosen, and its reliability values are compared with those of the first maximum likelihood path.
Another Viterbi decoder is described in U.S. Pat. No. 5,784,392 (hereinafter “U.S. Pat. No. '392).